/*
Date:20211208 17:31PM
key:1.第一次遍历先将新的next写入，同时做一个unordered_map映射新旧同一位置德节点
    2.第二次遍历观察原链表德每一个random，找到map里记录的新位置节点，并将新random指向新位置节点。(注意这里要先判断null再去map.find)
// Definition for a Node.
class Node {
public:
    int val;
    Node* next;
    Node* random;
    
    Node(int _val) {
        val = _val;
        next = NULL;
        random = NULL;
    }
};
*/
class Solution {
public:
    Node* copyRandomList(Node* head) {
        if(head==NULL){return NULL;}
        unordered_map<Node*,Node*>m;
        Node* head1=new Node(0);
        Node* p=head1;
        Node* p2=head;
        
        //主链表复制
        while(p2!=NULL)
        {
            m.insert(pair<Node*,Node*>(p2,p));
            p->val=p2->val;
            if(p2->next!=NULL)
            {
                p->next=new Node(0);
            }
            
            p=p->next;
            p2=p2->next;
        }
        p=head1;
        p2=head;
        //主链表复制
        while(p2!=NULL)
        {
            
            if(p2->random!=NULL)
            {
                auto tmp=m.find(p2->random);
                p->random=tmp->second;
            }
            
            p=p->next;
            p2=p2->next;
        }
        return head1;
    }
};